//
// Created by 123 on 2024/4/1.
//
/**
 * 堆排序
 *      首先建立小根堆
 *
 *
 *     更新 n 轮最小位置
 *     即成
 *
 *      O(nlog n)
 */
#include <iostream>

using namespace std;

#define MaxSize 100

typedef struct Array {
    int data[MaxSize];
    int length;
} Array, *Arr;

Array *initArray(int arr[], int len);

void swap(int &a, int &b);

void buildMaxHeap(Arr &arr, int len);

void heapAdjust(Arr &arr, int num_index, int len);
void heapify(Arr &arr,int num_index,int len);
void heapInsert(Arr &arr,int num);
void heapDelete(Arr &arr);

void heap_sort(Arr &arr);


int main() {
//    int a[10]{49, 38, 65, 97, 76, 13, 27, 49, 55, 4};
    int a[9]{23, 17, 72, 60, 25, 8,68, 71, 52};
    Arr arr = initArray(a, 9);
    buildMaxHeap(arr,arr->length);

//    heapInsert(arr,1);
    for (int i = 0; i < arr->length; ++i) {
        cout << arr->data[i] << "    ";
    }
    cout<<endl;
    heapDelete(arr);
    heapDelete(arr);
    for (int i = 0; i < arr->length; ++i) {
        cout << arr->data[i] << "    ";
    }
    cout<<endl;

    heap_sort(arr);

    for (int i = 0; i < arr->length; ++i) {
        cout << arr->data[i] << "    ";
    }
}

void heap_sort(Arr &arr) {
    buildMaxHeap(arr,arr->length);
    for (int i = arr->length-1; i >=0; --i) {
        swap(arr->data[0],arr->data[i]);
//        heapify(arr,0,i);
        heapAdjust(arr,0,i);
    }
}

void buildMaxHeap(Arr &arr, int len) {
    for (int i = (len-2)/2; i >=0 ; --i) {
//        heapify(arr,i,len);
        heapAdjust(arr,i,len);
    }

}

void heapAdjust(Arr &arr, int num_index, int len) {
    int num=arr->data[num_index];
    for (int i = num_index*2+1; i <len ; i=i*2+1) {
        if(i+1<len&&arr->data[i]>arr->data[i+1])
            i++;
        if(arr->data[i]>num)
            break;
        else{
            arr->data[num_index]=arr->data[i];
            num_index=i;
        }
        arr->data[num_index]=num;
    }
}
void heapify(Arr &arr,int num_index,int len){
    int left=num_index*2+1;
    while (left<len){
        int least=left+1<len&&arr->data[left+1]<arr->data[left]?left+1:left;
        least=arr->data[least]< arr->data[num_index]?least:num_index;
        if(least==num_index)
            break;
        swap(arr->data[least],arr->data[num_index]);
        num_index=least;
        left=least*2+1;
    }
}
void heapInsert(Arr &arr,int num){
    arr->data[arr->length++]=num;
    int len=(arr->length-1);
    while (arr->data[(len-1)/2]>arr->data[len]){
        swap(arr->data[(len-1)/2],arr->data[len]);
        len=(len-1)/2;
    }
}
void heapDelete(Arr &arr){
    swap(arr->data[0],arr->data[arr->length-1]);
    arr->length=arr->length-1;
    heapify(arr,0,arr->length);


}

Array *initArray(int arr[], int len) {
    Arr array = (Array *) malloc(sizeof(Array));
    for (int i = 0; i < len; ++i) {
        array->data[i] = arr[i];
    }
    array->length = len;
    return array;
}

void swap(int &a, int &b) {
    int turn = a;
    a = b;
    b = turn;
}